<?php
/**
 * Created by PhpStorm.
 * User: Elton
 * Date: 2021/5/31
 * Time: 15:31
 */

/**
 * 插入排序：
 * @param array $arr
 * @return array
 */
function insertSort(array $arr){

    $len = count($arr);
    for ($i = 0; $i < $len - 1; $i++) {

        // current 当前要插入的数据
        $current = $arr[$i];
        $j = $i;
        while ($j > 0 && $current > $arr[$j - 1]) {
            $arr[$j] = $arr[$j-1]; // 元素后移
            $j--;
        }
        $arr[$j] = $current; // 找到匹配的位置，将元素值插入

    }
    return $arr;

}

$a = [10, 30, 20, 50, 9, 19, 8];

print_r(insertSort($a));
